Many useful computer system applications incorporate graph data structures having nodes (i.e., vertices) and links between nodes (i.e., edges), for example, computer system applications that interact with networks, organizational structures and database schemas. As a result, graph management systems (GMS) of various types have become popular. A common GMS operation is the replication of a graph within or between graph management systems or, more generally, the synchronization of two graphs.
For the purposes of this description, graph management systems may be categorized into verified graph management systems (VGMS) and unverified graph management systems. Verified graph management systems may verify that a managed graph is in a valid state following each graph manipulation operation. For example, verified graph management systems may disallow graph manipulation operations that would result in links to nonexistent nodes or that would violate some other configured graph constraint. Examples of verified graph management systems include some lightweight directory access protocol (LDAP) servers and structured query language (SQL) servers.
A particular graph constraint that may result in difficulties when synchronizing graphs is an infrastructure link (or infrastructure edge) constraint. Infrastructure links are links that are (and in some cases, must be) created as part of the creation of an associated node. Examples of infrastructure links include LDAP schema class inheritance relationships and some other relationships utilized to define objects and classes of objects.
Problems may arise when replicating a cyclic graph (i.e., a graph having cycles or loops) to a verified graph management system. For example, it may not be possible, without modifying the cyclic graph, to create the nodes and associated infrastructure links of the cyclic graph at the verified graph management system in an order that avoids attempts to link to not-yet-existent nodes. If the verified graph management system disallows the creation of links to nonexistent nodes then it may not be possible to replicate the cyclic graph to the verified graph management system.
FIG. 1 illustrates a problem replicating a simple cyclic graph 100 to the example verified graph management system. Node 102 and infrastructure link 104 require that node 106 exist before they may be created. Node 106 and infrastructure link 108 require that node 110 exist before they may be created. However, node 110 and infrastructure link 112 require that node 102 exist before they may be created. As a result, there is no creation order for the nodes 102, 106 and 110, and their associated infrastructure links 104, 108 and 112, that avoids an attempt to create a link to a not-yet-existent node. It may not be possible to replicate the graph 100 to the verified graph management system.
In practice, graphs may be significantly more complex than graph 100. A further complication arises because of the variety of link types. There may be multiple categories of links in addition to infrastructure links including links that may change category if necessary, for example, to achieve replication and/or synchronization.